#include <stdio.h>
#include <stdlib.h>
#define maxsize 100
// 树的结构体
typedef struct BNode
{
    int data;
    BNode *lchild;
    BNode *rchild;
} BNode, *BTree;

typedef struct Queue
{
    BNode *data[maxsize];
    int rear, front;
} Queue;

// 对于二叉树中每个值为x的结点， 删除以他为根子树
void DelTree(BTree T)
{
    // if (T != NULL)
    // {
    //     DelTree(T->lchild);
    //     DelTree(T->rchild);
    //     printf("delete node： %d", T->data);
    //     free(T);
    // }
}
// 返回值：结点是否值为x
bool findAndDelNode(BTree &T, int x)
{
    if (T == NULL)
        return false;
    if (T->data == x){
        return true;
    }
    // 若孩子结点值为x 删除以该孩子结点为根的子树
    if (findAndDelNode(T->lchild, x))
    {
        DelTree(T->lchild);
        T->lchild = NULL;
    }
    if (findAndDelNode(T->rchild, x))
    {
        DelTree(T->rchild);
        T->rchild = NULL;
    }
    return false;
}

// 封装一层 处理若根结点为x时 直接删除整棵树
void DelNodeTree(BTree &T, int x)
{
    if (T == NULL)
        return;
    if (T->data == x)
    {
        DelTree(T);
        T = NULL;
        return;
    }
    findAndDelNode(T, x);
}

// 输出值为x的所有父节点
bool printParents(BTree T, int x)
{
    if (T == NULL)
        return false;
    if (T->data == x)
        return true;
    if (printParents(T->lchild, x) || printParents(T->rchild, x))
    {
        printf("%d ", T->data);
        return true;
    }
    return false;
}

// 测试
// 层序遍历
void PrintTree(BTree T)
{
    if (!T){
        printf("empty");
        return;
    }
    Queue q;
    q.rear = q.front = 0;

    q.data[q.rear] = T;
    q.rear = (q.rear + 1) % maxsize;

    while (q.rear != q.front)
    {
        int num = (q.rear - q.front + maxsize) % maxsize;
        for (int i = 0; i < num; i++)
        {
            printf("%d ", q.data[q.front]->data);
            if (q.data[q.front]->lchild)
            {
                q.data[q.rear] = q.data[q.front]->lchild;
                q.rear = (q.rear + 1) % maxsize;
            }
            if (q.data[q.front]->rchild)
            {
                q.data[q.rear] = q.data[q.front]->rchild;
                q.rear = (q.rear + 1) % maxsize;
            }
            q.front = (q.front + 1) % maxsize;
        }
        printf("\n");
    }
}

BNode *GetNode(int x)
{
    BNode *node = (BNode *)malloc(sizeof(BNode));
    node->data = x;
    node->lchild = NULL;
    node->rchild = NULL;
    return node;
}

int main()
{
    BTree T = GetNode(1);
    T->lchild = GetNode(2);
    T->rchild = GetNode(3);
    T->lchild->lchild = GetNode(4);
    T->rchild->rchild = GetNode(5);
    T->rchild->lchild = GetNode(6);
    PrintTree(T);
    DelNodeTree(T, 1);
    PrintTree(T);
    return 0;
}